package com.gong.suanfa.quickSort;

/**
 * @author GongChang
 * @version 1.0
 * @date 2021/6/8 0008 9:55
 */
public class RandomQuickSort {
    public static void main(String[] args) {
        int[] arr = {2,8,7,6,5,11,9,9,5};
        sort(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void sort(int[] arr,int start,int end){
        if (start >= end){
            return;
        }
        int t = start + (int)(Math.random()*(end-start+1));
        int l = start-1;
        int r = end+1;
        int index = start;

        while (index < r){
            if (arr[index] < arr[t]){
                swap(arr,index,l+1);
                index++;
                l++;
            }else if (arr[index] == arr[t]){
                index++;
            }else {
                swap(arr,index,r-1);
                r--;
            }
        }
        sort(arr,start,l);
        sort(arr,r,end);
    }

    private static void swap(int[] arr, int i, int i1) {
        int t = arr[i];
        arr[i] = arr[i1];
        arr[i1] = t;
    }
}
